Field of the Invention
The present invention relates to a histogram generation technique.
Description of the Related Art
Generating a histogram for input data is an effective method of acquiring statistic information of the input data (for example, identifying an input data value having a highest appearance frequency). In general, a histogram is generated using a storage element such as a memory or counter. For example, if a memory is used, a histogram is generated by storing a data value count (frequency value) is stored at a memory address corresponding to a data value. At this time, a value corresponding to the data value is read out from a low-speed memory (for example, a DRAM or the like) into a memory (for example, a cache memory or the like) accessible at high speed by a processing processor such as a CPU, the data value is added to the readout value, and the resultant value is written back in a low-speed memory such as a DRAM. With the above procedure, a histogram is generated. When generating such histogram, the following method is proposed as a method of shortening the memory access time.
According to Japanese Patent Laid-Open No. 2009-86761, a data area is read out into a high-speed memory using a memory having a hierarchical structure, thereby performing an addition operation. After adding input data, the data area is held on the high-speed memory. When the next input data is input, it is determined whether an area to be voted is on the high-speed memory. If the area is on a work memory, the area is voted continuously; otherwise, the area is replaced. Thus, the speed is increased.
According to Japanese Patent Laid-Open No. 6-36028, one input data is held. Then, when the next data coincides with the held data, 2 is added to the value of a bin. This decreases the access count to a memory, thereby increasing the speed.
According to Japanese Patent Laid-Open No. 2008-242733, some of a plurality of input data are masked to generate address data, a memory for generating a histogram is accessed according to the generated address, and 1 is added to count information identified by the address, thereby generating a histogram. With this method, it is only necessary to access one histogram instead of accessing a plurality of histograms, resulting in a decrease in access count to the memory. This can increase the speed.
One application of high-speed histogram generation is pattern recognition in the field of signal processing techniques. A method of determining the similarity between two images by obtaining the luminance histograms or color histograms of two images for which the similarity is to be calculated, and calculating the similarity between the color histograms is conventionally known as a method often used to calculate the similarity between two images.
A method of determining the similarity by calculating a histogram with respect to LBP (Local Binary Pattern) values obtained by coding the magnitude relationships with the luminance values of peripheral pixels is proposed in Timo Ahonen, Abdenour Hadid, and Matti Pietikainen, “Face recognition with local binary patterns, Computer Vision”, ECCV 2004 Proceedings, Lecture Notes in Computer Science 3021, Springer, 469-481. An LBP operator for a pixel (pixel of interest) at a position (xc, yc) is defined by:
                              LBP          ⁢                                          ⁢          8          ⁢                      (                                          x                c                            ,                              y                c                                      )                          =                              ∑                          n              =              0                        7                    ⁢                                          ⁢                                    s              ⁡                              (                                                      i                    n                                    -                                      i                    c                                                  )                                      ⁢                          2              n                                                          (        1        )                                          s          ⁡                      (            x            )                          =                  {                                                    1                                                                                  if                    ⁢                                                                                  ⁢                    x                                    ≥                  0                                                                                    0                                                                                  if                    ⁢                                                                                  ⁢                    x                                    <                  0                                                                                        (        2        )            where ic represents the luminance value of the pixel at the position (xc, yc), and in represents the luminance value of a pixel with an index=n among eight peripheral pixels. Note that n represents the index of the peripheral pixel. With respect to the position (xc, yc), n=7 is set for the upper left pixel and n is decremented by one in a clockwise direction. Equations (1) and (2) are merely an example of calculation of an LBP operator. There is also known an extended method in which a radius (the distance between the pixel of interest and a peripheral pixel) and a division count of the circumference of a circle with the radius are set as parameters.
A practical example of the calculation based on equations (1) and (2) will be described with reference to FIG. 2. When the pixel of interest (ic=96) at the central position (xc, yc) and its eight peripheral pixels are arranged as shown in the left view of FIG. 2, 1 or 0 is assigned according to the magnitude relationship (the right view of FIG. 2). The assigned value of 1 or 0 will be referred to a quantization value in a sense that binary quantization is performed for a difference value. A bit string obtained by arranging the quantization values will be referred to as a binary code. An LBP value is obtained by giving a weight of a power of 2 to the respective quantization values, and adding them. In the method described in Timo Ahonen, Abdenour Hadid, and Matti Pietikainen, “Face recognition with local binary patterns, Computer Vision”, ECCV 2004 Proceedings, Lecture Notes in Computer Science 3021, Springer, 469-481, face recognition processing is performed by setting a thus obtained LBP value as the index of each bin and calculating a histogram. An LBP value is calculated based on the magnitude relationship between luminance values, and is thus expected to be robust against an illumination variation, as compared with a simple luminance value.
As described above, there have been proposed various methods described in the background of the invention as a method of shortening the memory access time at the time of generating a histogram. However, the respective methods have the following problems.
In the method described in Japanese Patent Laid-Open No. 2009-86761, it is possible to increase the speed only for data in which each input data value gradually changes. If continuous input data do not exist in one area, a low-speed memory is accessed, and thus the speed cannot be increased.
In the method described in Japanese Patent Laid-Open No. 6-36028, it is possible to increase the speed only if continuous input data coincide with each other. If preceding and subsequent input data are different from each other, it is impossible to increase the speed.
In the method described in Japanese Patent Laid-Open No. 2008-242733, when it is not necessary to correctly vote, some of input data are masked by image processing or the like. This reduces bit information of the input data to generate a histogram at high speed. Since, however, the bit information is reduced, this method cannot be used when the information needs to be held.